According to the background art, it is known to represent a 3D scene with a mesh data structure. Various mesh data structure have been developed and optimized for a GPU usage. Data structures such as half-edge data representation, quad-trees, octo-trees, BVH, etc aim at efficiently encoding triangles information. While such a conservative approach permits to store every triangle of the mesh, it is also more complex to generate and to use than texture-based approaches. In this latter category of data structures, mesh information is encoded as a classical texture that is easily accessed on the GPU using shaders.
Among texture-based methods, Gu et al. introduced geometry images in “Geometry images” (in ACM Transactions on Graphics (TOG), volume 21, pages 355-361. ACM, 2002). Starting from a mesh, a surface parameterization is first computed so that the mesh is topologically equivalent to a disk. A geometry image is then generated by rendering the mesh into a texture using the uv parameterization instead of vertices positions. The result is a flat textured representation of the mesh where each pixel contains one interpolated vertex position value. Other information such as normal and texture coordinates may also be stored as per pixel values. This geometry image can then be used to approximately reconstruct the initial mesh.
Sanders et al. extended this work in “Multi-chart geometry images” (in proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processings, pages 146-155, Euro-graphics Association, 2003) to multi-charts geometry images to limit distortions introduced in Gu et al. To do this, multiple cuts are found over the mesh to extract various charts parameterized independently. The charts are then distributed all over the texture through a chart placement algorithm. Finally, the classical geometry images rendering is applied in a first pass to generate the multi-charts geometry image. As rasterization on the border of the two adjacent charts may give different values on each chart, they apply a border zippering algorithm. The algorithm avoids cracks and ensures continuity at chart borders. In a second pass, a one-pixel large border is created around each chart to force neighboring charts to share the exact same border. Better reconstructions are obtained, minimizing distortion artifacts.
Geometry images have been used for efficient ray-tracing of meshes on the GPU, proving this structure suitable for the GPU. However, while the reconstruction based on multi-chart geometry image is seamless due to the border zippering, each chart of the geometry image is independent from its neighbors. This representation does not allow jumping from a chart to another at run-time. For instance, being on border pixel of a source chart of the geometry image, there is no solution to find its neighbor in a destination chart. While geometry images are good mesh data structure for fast GPU access, it is impossible to use such representation to arbitrarily move around the object because charts are always independent.